package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import org.junit.Test;

public class Q1927 {
	
	//Time Limit Exceeded
    /**
     * @param nums: a list of integers
     * @return: return a list of integers
     */
    public List<Integer> countSmaller(int[] nums) {
        // write your code here
    	if (nums == null || nums.length == 0) {
			return new ArrayList<>();
		}
    	Node root = new Node();
    	root.index = 0; 
    	root.value = nums[0];
    	for(int i = 1; i < nums.length; i ++) {
    		insertNode(i, nums, root);
    	}
    	Integer [] rs = new Integer[nums.length];
    	Stack<Node> stack = new Stack<>();
    	stack.add(root);
    	while(!stack.isEmpty()) {
    		Node node = stack.pop();
    		rs[node.index] = node.smallCount;
    		if(node.left != null) {
    			stack.push(node.left);
    		}
    		if(node.right != null) {
    			stack.push(node.right);
    		}
    	}
    	return Arrays.asList(rs);
    }

    private Node insertNode(int i, int[] nums, Node node) {
		if (node == null) {
			node = new Node();
			node.index = i; 
			node.value = nums[i];
		}else {
			if (node.value > nums[i]) {
				node.smallCount = node.smallCount + 1;
				node.left = insertNode(i, nums, node.left);
				count(node.right);
			}else if(node.value == nums[i]){
				node.right = insertNode(i, nums, node.right);
			}else {
				node.right = insertNode(i, nums, node.right);
			}
		}
		return node;
	}

	private void count(Node right) {
		if(right == null) {
			return;
		}
		Stack<Node> stack = new Stack<>();
    	stack.add(right);
    	while(!stack.isEmpty()) {
    		Node node = stack.pop();
    		node.smallCount = node.smallCount + 1;
    		if(node.left != null) {
    			stack.push(node.left);
    		}
    		if(node.right != null) {
    			stack.push(node.right);
    		}
    	}
	}

	public class Node{
    	int value;
    	int index;
    	Node left;
    	Node right;
    	int smallCount;
    }

	@Test
	public void testCountSmaller() {
		int []nums = {5,2,6,1};
		System.out.println(countSmaller(nums));
	}
}
